Search Results

Documents authored by Studený, Milan


Document
Algorithmic Aspects of Information Theory (Dagstuhl Seminar 22301)

Authors: Phokion G. Kolaitis, Andrej E. Romashchenko, Milan Studený, Dan Suciu, and Tobias A. Boege

Published in: Dagstuhl Reports, Volume 12, Issue 7 (2023)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22301 "Algorithmic Aspects of Information Theory". Constraints on entropies constitute the "laws of information theory". These constraints go well beyond Shannon’s basic information inequalities, as they include not only information inequalities that cannot be derived from Shannon’s basic inequalities, but also conditional inequalities and disjunctive inequalities that are valid for all entropic functions. There is an extensive body of research on constraints on entropies and their applications to different areas of mathematics and computer science. So far, however, little progress has been made on the algorithmic aspects of information theory. In fact, even fundamental questions about the decidability of information inequalities and their variants have remained open to date. Recently, research in different applications has demonstrated a clear need for algorithmic solutions to questions in information theory. These applications include: finding tight upper bounds on the answer to a query on a relational database, the homomorphism domination problem and its uses in query optimization, the conditional independence implication problem, soft constraints in databases, group-theoretic inequalities, and lower bounds on the information ratio in secret sharing. Thus far, the information-theory community has had little interaction with the communities where these applications have been studied or with the computational complexity community. The main goal of this Dagstuhl Seminar was to bring together researchers from the aforementioned communities and to develop an agenda for studying algorithmic aspects of information theory, motivated from a rich set of diverse applications. By using the algorithmic lens to examine the common problems and by transferring techniques from one community to the other, we expected that bridges would be created and some tangible progress on open questions could be made.

Cite as

Phokion G. Kolaitis, Andrej E. Romashchenko, Milan Studený, Dan Suciu, and Tobias A. Boege. Algorithmic Aspects of Information Theory (Dagstuhl Seminar 22301). In Dagstuhl Reports, Volume 12, Issue 7, pp. 180-204, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Article{kolaitis_et_al:DagRep.12.7.180,
  author =	{Kolaitis, Phokion G. and Romashchenko, Andrej E. and Studen\'{y}, Milan and Suciu, Dan and Boege, Tobias A.},
  title =	{{Algorithmic Aspects of Information Theory (Dagstuhl Seminar 22301)}},
  pages =	{180--204},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{7},
  editor =	{Kolaitis, Phokion G. and Romashchenko, Andrej E. and Studen\'{y}, Milan and Suciu, Dan and Boege, Tobias A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.7.180},
  URN =		{urn:nbn:de:0030-drops-176155},
  doi =		{10.4230/DagRep.12.7.180},
  annote =	{Keywords: Information theory, Information inequalities, Conditional independence structures, Database query evaluation and containment, Decision problems}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail